package org.blogwu.learn.leetcode.二叉树;

import org.blogwu.learn.algorithm.树.二叉搜索树.printer.BinaryTrees;

import java.util.concurrent.ConcurrentLinkedQueue;

public class _226_翻转二叉树 {

    public static void main(String[] args) {
        Integer[] sz = {4, 2, 7, 1, 3, 6, 9};
        TreeNode root = TreeNode.convert(sz);
        BinaryTrees.print(root);
        System.out.println("");
        root = invertTree2(root);
        BinaryTrees.print(root);
        System.out.println("");
    }


    public static TreeNode invertTree(TreeNode root) {
        if (root == null) return root;
        // 交换一下左右
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }


    public static TreeNode invertTree2(TreeNode root) {
        if (root == null) return root;
        ConcurrentLinkedQueue<TreeNode> queue = new ConcurrentLinkedQueue<>();
        queue.offer(root);
        int num = 1;
        while (!queue.isEmpty()) {
            TreeNode mm = queue.poll();
            num--;
            TreeNode temp = mm.left;
            mm.left = mm.right;
            mm.right = temp;
            if (mm.left != null) queue.offer(mm.left);
            if (mm.right != null) queue.offer(mm.right);
            if (num == 0) {
                num = queue.size();
            }
        }
        return root;
    }

}
